The invention relates to the field of data transmissions and in particular to devices and methods which provide packet network address resolution.
Address resolution is a key function of network equipment such as routers and switches. The source, destination, and media access rights of network packets are usually determined using the addresses contained within the packets. Usually, forwarding decisions, such as where to deliver a data packet, are made based on at least one of the addresses carried in the data packet. These addresses are used as the key to determine from a database, containing address dependent information, which egress or exit port the packet should be sent to, or more generally, how the packet should be processed. Given that the forwarding decision is to be made for each packet, address resolution must therefore be performed for each packet. Address resolution entails extracting the different addresses from within the packet and using these addresses in a database lookup procedure to find the required routing information. The database lookup procedure can require up to several lookup operations based on source and destination addresses of several network protocol layers. Because modern switches and routers need to deal with a number of ports running at high speed, with each port receiving or transmitting multiple pockets, providing fast address resolution becomes a challenging problem to solve.
The problem of fast address resolution is exacerbated by the numerous lookup procedures used to perform required network routing functions such as MAC (medium access control) lookup and IP (internet protocol) longest prefix match lookup. Procedures such as hashing, multi-stage table lookup, and caching have been developed to perform these functions.
Ethernet layer 2 MAC address lookup and layer 3 IP longest prefix match are required in numerous networks. In the Ethernet standard, each network device is assigned a unique hexadecimal serial number, a MAC address, which identifies it on the network. Because of this scheme and the uniqueness of the MAC address of every device on the network, each network device can monitor network traffic and look for its own MAC address in each packet to determine if that packet should be decoded or not. Specific network devices, such as routers, switches and bridges, are able to determine the network source and destination of a packet simply by monitoring the MAC addresses within that packet. With this data, the network device can determine whether the packet should be decoded or not. By way of an example, a learning bridge can, by monitoring MAC addresses in packets, determine which addresses are on which side of a connection. By monitoring the source and destination MAC addresses in packets, a learning bridge can determine, when it receives a packet, whether that packet must cross the bridge or not.
Given the number of packets a network device receives, a fast MAC address lookup is desirable. One widely used procedure for MAC address lookup has been hashing. By way of example, if we wish to have B classes numbered 0,1, . . . , B-1, then we use a hash function h such that for each object x, h(x) is one of the integers 0 through B-1. The value of h(x) is the class to which x belongs. x is therefore the key and h(x) is the hash value of x. The xe2x80x9cclassesxe2x80x9d are normally referred to as buckets such that it is customary to refer to x as belonging to bucket h(x).
With respect to MAC address lookup, such a hash structure is used. FIG. 1 illustrates the procedure. The 48 bit MAC address 10 is used to calculate a hash key 20 that indexes the hash table 30. Each hash table entry 40 contains a head pointer to the linked list of hash buckets 50 for the MAC addresses with the same hash key. The hash bucket header contains the MAC address 55, the next pointer for the linked list 57, and the forwarding context data structure 59 that is defined by the application that uses the address resolution system.
The MAC address lookup procedure begins with the address extraction. The MAC address is extracted by simple offsettingxe2x80x94the MAC address is found at a specific predetermined offset from the beginning of each packet. The extracted MAC address 10 is used to calculate the hash key 20. The head pointer of the hash bucket chain is fetched from the hash table 30 using the hash key 20. The address resolution system recursively fetches the hash bucket header and compares the MAC address stored in the bucket header with the MAC address that is being looked up until either a match is found or the end of the linked list is reached. After finding a match, the address resolution system fetches the remaining part of the hash bucket and presents it as the lookup result.
IP addresses, on the other hand, are the actual addresses which determine the logical location of a network node on the network. Routers, devices which determine the route a packet must take to reach its destination IP address, must correctly determine for each incoming packet which port to send the packet and the next hop that packet must take. For each incoming packet, a search must be performed in the router""s forwarding table to determine which next hop the packet is destined for.
One longest prefix match procedure that combines speed with ease of hardware implementability is the multistage lookup procedure outlined by Gupta et al. in xe2x80x9cRouting Lookups in Hardware at Memory Access Speedsxe2x80x9d, IEEE Infocom, April 1998. A modified version of the Gupta et al procedure simplifies the lookup procedure and simplifies its implementation.
In this modified version of the Gupta et al procedure, conceptually illustrated in FIG. 3, the IP address database contains three separate route tables and the route context table. The route tables RT0, RT1, and RT2 are segmented to provide for routes of various prefix lengths. Route table RT0 provides for all routes of prefix length 17 or less while route table RT1 provides for all routes of prefix length 18 to 24 and route table RT2 provides for routes of prefix length 25 and longer. All three route tables contain entries of identical format as shown in FIG. 2. Each entry has two 16-bit records, each record containing two control bits, a VALID bit 62 and an INDIRECT bit 64, and a 14-bit memory index 66. The base addresses for the route tables are predetermined and set, making it easier to reference each route table independent of the others. Once the correct route is found, the memory pointer in the record points to an entry in the Route Context table RC. (It should be noted that in this example, a 32-bit memory width is assumed. Thus, each route table entry can accomodate two 16-bit records. However, this procedure can be adapted for implementation in any computer system. Ideally, each route table can be seen as simply a collection of 16-bit records.) Given a destination IP address, the procedure begins by extracting the most significant 17-bits 72 of the destination IP address contained in the input packet. The predetermined base address 73 of the first route table RT0 is added to the 17 bits 72 extracted from the given destination IP address, thereby forming a complete memory address 74 to a selected entry in the first route table RT0. This first route table RT0 contains entries for all established routes of 17-bit prefix length or less.
As noted above, each entry in the first route table RT0 contains a 14 bit memory index 66. For routes with prefix length 17 bits or less, the memory index 66 is a pointer into a route context table RC. For routes longer than 17 bits, the INDIRECT control bit 64 in the route table RT0 entry is set, indicating that the 14 bit memory index 66 contained in the route table RT0 table entry is to be used as a pointer to index into a second route table RT1. The index into route table RT1 from the route table RT0 table entry is concatenated with the following 7 bits 75 of the given destination IP address and the predetermined base address 76 of the second route table RT1 to form a complete address 77 of a selected entry in the second route table RT1.
Since this second route table RT1 contains entries having the same format as the entries in the first route table RT0, the INDIRECT control bit 64 in the entry in route table RT1 designates whether the memory index 66 in the route table RT1 entry points to an entry in the route context table RC or whether it is to be used as an index into a third route table RT2. For routes of prefix lengths 18-24 the INDIRECT control bit 64 in the route table RT1 entry should not be set, thereby indicating that the memory index 66 in the route table RT1 entry should point to an entry in the route context table RC. For routes with a prefix length longer than 24, the INDIRECT control bit 64 should be set, thereby indicating that the memory index 66 in the route table RT1 entry is to be used as a pointer to index a third route table RT2.
If the INDIRECT bit 64 is set in the entry in the second route table RT1, the least significant 8 bits 78 of the given destination IP address is concatenated with the memory index 66 found in the selected route table RT1 entry and the predetermined base address 79 of the third route table RT2, thereby forming a complete address 81 of an entry in the third route table RT2. In this third and final route table RT2, the INDIRECT bit 64 is not used and the memory index 66 contained in the entry is used to index into the route context table RC.
If, in any of the above steps, the VALID bit 62 is not set, then the IP address being searched for is invalid and the search must terminate. If a specific IP address does not have an entry in the route table RT2, even after passing through route tables RT1 and RT0, then that specific IP address is considered invalid and the search also terminates.
The route context table RC contains the addresses of exit ports. Through the modified Gupta et al procedure outlined above, an entry in the route context table RC is selected for a given destination IP address, thereby determining which exit port should be used by a packet with the given destination IP address. This defines the next hop that the data packet must take.
Given the above procedure, the steps taken to find a route context will be illustrated.
By way of example, assume that the route context RC table entries for six destination IP addresses A,B,C,D,E,and F are to be determined. For simplicity, assume that X17 refers to the most significant 17 bits of the IP address X, that X7 refers to the following 7 bits of the destination IP address X, and that X8 refers to the least significant 8 bits of the same address. For this example, we can assume that the table entries for RT0, RT1, and RT2 are as shown in FIG. 4 following the format outlined in FIG. 2. For this example, the following examples will have the following meanings :
BARTxxe2x80x94Base address of Rtx
RT0(x)xe2x80x94entry x in route table RT0 (similar notations will be used for the other route tables and for the route context table)
Taking IP address A first, if BART0+A17xe2x88x92 greater than RT0(3) (meaning that adding the base address of RT0 to the most significant 17 bits of A yields entry 3 in RT0), then the index to RT1 is 5.
Therefore, from the table entries in FIG. 4,
BART0+A17xe2x88x92 greater than RT0(3)= greater than BART1+5+A7xe2x88x92 greater than RT1(5+A7)= greater than RC(112)
This means that the final end result is entry 112 in the Route Context table.
Similarly, we can follow the following operations for the other addresses:
BART0+B17xe2x88x92 greater than RT0(5)xe2x88x92 greater than RC(100)
BART0+C17xe2x88x92 greater than RT0(8)=BART1+7+C7xe2x88x92 greater than RT1(7)xe2x88x92 greater than INVALID
BART0+D17xe2x88x92 greater than RT0(7)xe2x88x92 greater than INVALID
BART0+E17xe2x88x92 greater than RT0(6)xe2x88x92 greater than RC(110)
BART0+F17xe2x88x92 greater than RT0(4)=BART1+6+F7xe2x88x92 greater than RT1(6+F7)=BART2+12+F8xe2x88x92 greater than RT2(12)xe2x88x92 greater than RC(119)
We can summarize the results of the search for the route contexts of the addresses as follows:
Axe2x88x92 greater than RC(112)
Bxe2x88x92 greater than RC(100)
Cxe2x88x92 greater than INVALID
Dxe2x88x92 greater than INVALID
Exe2x88x92 greater than RC(110)
Fxe2x88x92 greater than RC(119)
The two above procedures for MAC address lookup and IP longest prefix match suffer from one drawback or another when implemented in either hardware or software using traditional methods used to increase the throughput of an address resolution system.
One traditional method is the use of a sequential processing unit. In this method, the logic is designed to follow the control path of the look-up flow chart with the address resolution process being completed in sequential steps, including database lookup and address extraction. Unfortunately, this method provides a low throughput.
Another traditional method is the use of a pipelined processing unit. In this method, the address resolution process is divided into a fixed number (N) of steps with the search context being passed along the pipeline as each step of the processing is completed. At most, N address look-up threads can be processed in parallel. However, to have an efficient pipeline, the process must be divided into a fixed number of processing stages with each stage requiring an equal amount of processing time. Unfortunately, most hash look-up procedures and multistage memory look procedures have an indeterministic but bounded number of look-up steps, with the next step being determined by the intermediate result of the previous step. The dynamic nature of such procedures therefore makes this static pipelining approach unsuitable.
A third method uses a channelized processing unit. Multiple parallel instances of this processing unit is replicated in a multi-channel system with each channel comprising separate address resolution search engines running in parallel to other channels. Ideally, system performance should scale with the number of processing units. However, this is not the case. Given N instances of identical processing units, the actual system performance speedup is between log2N and N/ln N (see Computer Architecture and Parallel Processing, K Hwang and Briggs, McGraw-Hill Publishing company, 1984, pp 27-29). Also, this method can be quite expensive given that either multiple parallel instances of RAM must be used to store the look-up database or a multi-port shared memory access controller is required to arbitrate the memory accesses among the search engines. While the multi-port shared memory structure may be efficient, having multiple separate search engines along with a memory access controller with a large number of ports is not.
Accordingly, given the unsuitability, inefficiency, and cost considerations of the traditional methods used to increase the speed of address resolution systems, what is required is a method or device that can be used with different lookup procedures such as hashing and multistage lookup without incurring the drawbacks of the traditional methods.
The present invention is a method and a module for executing different database lookup procedures for resolving network addresses. Separate modules are used for each database lookup procedure allowing multiple, independent lookup procedures to be implemented on the same system. Within each module, at least two processing units, each processing unit operating independently of one another and each processing unit coupled to a memory and to one another by data pipelines, divide the database lookup procedure into multiple stages. A feedback loop between at least two of these processing units is implemented using data pipelines, thereby allowing complex branching and looping functions between the processing units. Also within the modules, the data pipelines and the independently operating processing units allow multiple database lookup threads to execute independently of one another, thereby increasing system throughput.
By having at least two processing units per module, the modules are scalable within themselves and hence adaptable to different database lookup procedures. Furthermore, the feedback loop within the module allows for the implementation of database lookup procedures that have a dynamic number of steps.
Data pipelines also couple separate modules, allowing data exchange between the modules.
It should be noted that for the purposes of this application a data pipeline is defined as a hardware device or a software data structure that has the properties of a queue or of a FIFO (first-in first-out) list or register. By this definition, a data pipeline receives all incoming data at a receiving end and buffers this data in the order the data was received. The data pipeline then transmits the buffered data at a transmitting end, again in the order in which the data was received.
It should also be noted that a search context for the purposes of this application is defined as data required not only to identify a search but also to define that search. A search context therefore includes a search identifier that identifies the specific search thread in a multithreaded search system and search parameters that determine not only what is being sought but also determines the scope of that search.
In accordance with an embodiment of the invention, a module for executing a multiple step database lookup procedure includes a plurality of processing units, each processing unit executing at least one step in the multiple step database lookup procedure with at least two processing units being coupled to a memory containing a database and having multiple input and output ports, and a plurality of data pipelines which couple the plurality of processing units to each other and to external modules.
In accordance with another embodiment of the invention, a device for resolving the routing of network packets, with each packet containing at least one network address, includes a search engine comprised of a plurality of modules including at least one search module, each search module executing a specific database search lookup procedure which retrieves from a memory data related to the at least one network address.
In accordance with a third embodiment of the invention, a method of executing a multiple step address resolution procedure comprises:
a) receiving a search context at a search unit,
b) initiating a memory request using search data contained in the search context,
c) transmitting the search context to a compare unit,
d) receiving data at the compare unit, said data including:
the search context,
a memory result of the memory request initiated by the search unit,
e) determining at the compare unit if further searching is required based on the memory result and search data contained in the search context,
f) modifying at the compare unit the search context to produce a modified search context based on the memory result and if further searching is required,
g) transmitting the modified search context to the search unit if further searching is required,
h) transmitting the modified search context to an external unit if further searching is not required.